package com.dhu.graph.shortestPath;

import com.dhu.graph.basic.GraphImpls.EdgeWeightedDiGraph;
import com.dhu.graph.basic.edge.DirectedEdge;
import com.dhu.graph.utils.IndexMinPQ;

import java.nio.channels.Channel;
import java.util.Stack;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-13
 * @ Description：
 * 1.Dijskatra算法能够解决边权重非负的加权有向图的单起点最短路径问题
 * 2.找出一副加权有向图的最小路径生成树。依赖一个索引最小优先队列pq,distTo[] distTo[v]表示从起点s到v的距离(各条边的权重
 * 之和），edgeTO[]和前面的算一样，是一种记录路径的方式.
 * 3.算法思路：
 * distTo[0]用0来初始化，其他的顶点的distTo[]用正无穷来初始化。
 * 开始先将起点s加入最小生成树（实际不做任何的动作，一种抽象的理解），并把起点s指向的顶点的边全都加入到优先队列，封装载relax方法中（由于用inf来初始化）
 * 然后从第二次循环开始进入第二个阶段，从优先队列中删除并返回权重最小的边e，然后遍历e.to的邻接表，经过relax方法的动作
 * 如果e的邻接表中的顶点w=e.to, 如果distTo[w] > dist[v = e.from] + e.weight,distT0[w]为初始化的inf或者上次计算出来的
 * 最小路径，如果上式满足那么说明访问的到w新路径要比上次计算中访问到w的路径要端，这时采取的两个动作是，记录最路径最小生成树的数组
 * edgeTo[w] = e,这可能是一次新的记录也可能是对上次记录的修改；如果顶点w已经在pq中那么修改权重，因为到w的路径已经改变了
 * 如果还没在队列中那么将它加入队列。
 * 可见队列pq的作用是维持遍历顶点的顺序，保证从由s触发向外扩散的路径是局部的最短路径，所有的局部最小路径 == 全局的最短路径
 * 4.Dijkastra算法也可以解决加权无向图的单起点最短路径问题，只需把无向边替换为两个方向相反的有向边即可。
 * @ Modified By：
 * @ Version:
 */
public class DijkastraSP {
    private IndexMinPQ<Double> pq;
    private double[] distTo;
    private DirectedEdge[] edgeTo;

    public DijkastraSP(EdgeWeightedDiGraph G,int s){
        int sz = G.V();
        this.pq = new IndexMinPQ<>(sz);
        this.distTo = new double[sz];
        this.edgeTo = new DirectedEdge[sz];

        distTo[s] = 0.0;
        for (int z = 0; z < sz; z++) {
            distTo[z] = Double.POSITIVE_INFINITY;
        }
        pq.insert(0,0.0);

        while(!pq.isEmpty())
            relax(G, pq.delMin());
    }

    private void relax(EdgeWeightedDiGraph G, int v){
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            // distTo[w]初始值是inf,所以不满足次条件时e已经在当前生成的最小生成树中edgeTo[]中或者e是一条失效边 ，w已经在树中
            if (distTo[w] > distTo[v] + e.getWeight()){
                distTo[w] = distTo[v] + e.getWeight();
                edgeTo[w] = e;

                if (pq.contains(w)) pq.change(w, e.getWeight());
                else pq.insert(w,e.getWeight());
            }
        }
    }
    public boolean hasPathTo(int v){
        return this.distTo[v] < Double.POSITIVE_INFINITY;
    }
    public double distTo(int v){
        return this.distTo[v];
    }
    public Iterable<DirectedEdge> pathTo(int v){
        if (!hasPathTo(v)) return null;
        Stack<DirectedEdge> edges = new Stack<>();
        for (DirectedEdge e  = edgeTo[v]; e != null; e = edgeTo[e.from()]){
            edges.push(e);
        }
        return edges;
    }
}
